/// <remarks>
/// The contents of this file are derived from work by Matthias Hertel at:
/// http://www.mathertel.de/Diff/
/// It has been modifed to exclude functionality not required and to bring 
/// coding style in line with the rest of the Subversion Reports project.
/// The license for this file differs from that of the rest of the Subversion Reports project
/// in that it is a BSD License, whereas Subversion Reports is released under the GPL.
/// </remarks>

/// <license>
/// Software License Agreement (BSD License)
/// Copyright (c) 2005-2007 by Matthias Hertel, http://www.mathertel.de/
/// All rights reserved.
/// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
///    * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
///    * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
///    * Neither the name of the copyright owners nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
/// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
/// </license>

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text.RegularExpressions;

namespace SubversionReports.Utilities
{
    /// <summary>
    /// This Class implements the Difference Algorithm published in
    /// "An O(ND) Difference Algorithm and its Variations" by Eugene Myers
    /// Algorithmica Vol. 1 No. 2, 1986, p 251.  
    /// 
    /// There are many C, Java, Lisp implementations public available but they all seem to come
    /// from the same source (diffutils) that is under the (unfree) GNU public License
    /// and cannot be reused as a sourcecode for a commercial application.
    /// There are very old C implementations that use other (worse) algorithms.
    /// Microsoft also published sourcecode of a diff-tool (windiff) that uses some tree data.
    /// Also, a direct transfer from a C source to C# is not easy because there is a lot of pointer
    /// arithmetic in the typical C solutions and i need a managed solution.
    /// These are the reasons why I implemented the original published algorithm from the scratch and
    /// make it avaliable without the GNU license limitations.
    /// I do not need a high performance diff tool because it is used only sometimes.
    /// I will do some performace tweaking when needed.
    /// 
    /// The algorithm itself is comparing 2 arrays of numbers so when comparing 2 text documents
    /// each line is converted into a (hash) number. See DiffText(). 
    /// 
    /// Some chages to the original algorithm:
    /// The original algorithm was described using a recursive approach and comparing zero indexed arrays.
    /// Extracting sub-arrays and rejoining them is very performance and memory intensive so the same
    /// (readonly) data arrays are passed arround together with their lower and upper bounds.
    /// This circumstance makes the LCS and SMS functions more complicate.
    /// I added some code to the LCS function to get a fast response on sub-arrays that are identical,
    /// completely deleted or inserted.
    /// 
    /// The result from a comparisation is stored in 2 arrays that flag for modified (deleted or inserted)
    /// lines in the 2 data arrays. These bits are then analysed to produce a array of Item objects.
    /// 
    /// Further possible optimizations:
    /// (first rule: don't do it; second: don't do it yet)
    /// The arrays DataA and DataB are passed as parameters, but are never changed after the creation
    /// so they can be members of the class to avoid the paramter overhead.
    /// In SMS is a lot of boundary arithmetic in the for-D and for-k loops that can be done by increment
    /// and decrement of local variables.
    /// The DownVector and UpVector arrays are alywas created and destroyed each time the SMS gets called.
    /// It is possible to reuse tehm when transfering them to members of the class.
    /// See TODO: hints.
    /// 
    /// diff.cs: A port of the algorythm to C#
    /// Copyright (c) by Matthias Hertel, http://www.mathertel.de
    /// This work is licensed under a BSD style license. See http://www.mathertel.de/License.aspx
    /// 
    /// Changes:
    /// 2002.09.20 There was a "hang" in some situations.
    /// Now I undestand a little bit more of the SMS algorithm. 
    /// There have been overlapping boxes; that where analyzed partial differently.
    /// One return-point is enough.
    /// A assertion was added in CreateDiffs when in debug-mode, that counts the number of equal (no modified) lines in both arrays.
    /// They must be identical.
    /// 
    /// 2003.02.07 Out of bounds error in the Up/Down vector arrays in some situations.
    /// The two vetors are now accessed using different offsets that are adjusted using the start k-Line. 
    /// A test case is added. 
    /// 
    /// 2006.03.05 Some documentation and a direct Diff entry point.
    /// 
    /// 2006.03.08 Refactored the API to static methods on the Diff class to make usage simpler.
    /// 2006.03.10 using the standard Debug class for self-test now.
    ///            compile with: csc /target:exe /out:diffTest.exe /d:DEBUG /d:TRACE /d:SELFTEST Diff.cs
    /// 2007.01.06 license agreement changed to a BSD style license.
    /// 2007.06.03 added the Optimize method.
    /// 2007.09.23 UpVector and DownVector optimization by Jan Stoklasa ().
    /// </summary>

    public class Diff
    {
        /// <summary>details of one difference.</summary>
        public struct Item
        {
            /// <summary>Start Line number in Data A.</summary>
            public int StartA;
            /// <summary>Start Line number in Data B.</summary>
            public int StartB;

            /// <summary>Number of changes in Data A.</summary>
            public int DeletedA;
            /// <summary>Number of changes in Data B.</summary>
            public int InsertedB;
        }

        /// <summary>
        /// Shortest Middle Snake Return Data
        /// </summary>
        private struct ShortestMiddleSnake
        {
            internal int x, y;
            // internal int u, v;  // 2002.09.20: no need for 2 points 
        }

        /// <summary>
        /// Find the difference in 2 texts, comparing by textlines.
        /// </summary>
        /// <param name="textA">A-version of the text (usualy the old one)</param>
        /// <param name="textB">B-version of the text (usualy the new one)</param>
        /// <returns>Returns a array of Items that describe the differences.</returns>
        public List<Item> DiffText(string textA, string textB)
        {
            return (DiffText(textA, textB, false, false, false));
        }


        /// <summary>
        /// Find the difference in 2 text documents, comparing by textlines.
        /// The algorithm itself is comparing 2 arrays of numbers so when comparing 2 text documents
        /// each line is converted into a (hash) number. This hash-value is computed by storing all
        /// textlines into a common hashtable so i can find dublicates in there, and generating a 
        /// new number each time a new textline is inserted.
        /// </summary>
        /// <param name="textA">A-version of the text (usualy the old one)</param>
        /// <param name="textB">B-version of the text (usualy the new one)</param>
        /// <param name="trimSpace">When set to true, all leading and trailing whitespace characters are stripped out before the comparation is done.</param>
        /// <param name="ignoreSpace">When set to true, all whitespace characters are converted to a single space character before the comparation is done.</param>
        /// <param name="ignoreCase">When set to true, all characters are converted to their lowercase equivivalence before the comparation is done.</param>
        /// <returns>Returns a array of Items that describe the differences.</returns>
        public static List<Item> DiffText(string textA, string textB, bool trimSpace, bool ignoreSpace, bool ignoreCase)
        {
            // prepare the input-text and convert to comparable numbers.
            Hashtable h = new Hashtable(textA.Length + textB.Length);

            // The A-Version of the data (original data) to be compared.
            DiffData dataA = new DiffData(DiffCodes(textA, h, trimSpace, ignoreSpace, ignoreCase));

            // The B-Version of the data (modified data) to be compared.
            DiffData dataB = new DiffData(DiffCodes(textB, h, trimSpace, ignoreSpace, ignoreCase));

            int max = dataA.Length + dataB.Length + 1;
            /// vector for the (0,0) to (x,y) search
            int[] downVector = new int[2 * max + 2];
            /// vector for the (u,v) to (N,M) search
            int[] upVector = new int[2 * max + 2];

            LongesCommonSubsequence(dataA, 0, dataA.Length, dataB, 0, dataB.Length, downVector, upVector);

            Optimize(dataA);
            Optimize(dataB);
            return CreateDiffs(dataA, dataB);
        }


        /// <summary>
        /// If a sequence of modified lines starts with a line that contains the same content
        /// as the line that appends the changes, the difference sequence is modified so that the
        /// appended line and not the starting line is marked as modified.
        /// This leads to more readable diff sequences when comparing text files.
        /// </summary>
        /// <param name="data">A Diff data buffer containing the identified changes.</param>
        private static void Optimize(DiffData data)
        {
            int startPosition;

            startPosition = 0;
            while (startPosition < data.Length)
            {
                while ((startPosition < data.Length) && (data.Modified[startPosition] == false))
                    startPosition++;
                int endPosition = startPosition;
                while ((endPosition < data.Length) && (data.Modified[endPosition]))
                    endPosition++;

                if ((endPosition < data.Length) && (data.Data[startPosition] == data.Data[endPosition]))
                {
                    data.Modified[startPosition] = false;
                    data.Modified[endPosition] = true;
                }
                else
                {
                    startPosition = endPosition;
                }
            }
        }

        /// <summary>
        /// Find the difference in 2 arrays of integers.
        /// </summary>
        /// <param name="arrayA">A-version of the numbers (usualy the old one)</param>
        /// <param name="arrayB">B-version of the numbers (usualy the new one)</param>
        /// <returns>Returns a list of Items that describe the differences.</returns>
        public static List<Item> DiffInt(int[] arrayA, int[] arrayB)
        {
            // The A-Version of the data (original data) to be compared.
            DiffData dataA = new DiffData(arrayA);

            // The B-Version of the data (modified data) to be compared.
            DiffData dataB = new DiffData(arrayB);

            int max = dataA.Length + dataB.Length + 1;
            /// vector for the (0,0) to (x,y) search
            int[] downVector = new int[2 * max + 2];
            /// vector for the (u,v) to (N,M) search
            int[] upVector = new int[2 * max + 2];

            LongesCommonSubsequence(dataA, 0, dataA.Length, dataB, 0, dataB.Length, downVector, upVector);
            return CreateDiffs(dataA, dataB);
        }


        /// <summary>
        /// This function converts all textlines of the text into unique numbers for every unique textline
        /// so further work can work only with simple numbers.
        /// </summary>
        /// <param name="text">the input text</param>
        /// <param name="h">This extern initialized hashtable is used for storing all ever used textlines.</param>
        /// <param name="trimSpace">ignore leading and trailing space characters</param>
        /// <param name="ignoreSpace">if set to <c>true</c> [ignore space].</param>
        /// <param name="ignoreCase">if set to <c>true</c> [ignore case].</param>
        /// <returns>a array of integers.</returns>
        private static int[] DiffCodes(string text, IDictionary h, bool trimSpace, bool ignoreSpace, bool ignoreCase)
        {
            string[] lines = text.Replace("\r", "").Split('\n');// strip off all cr, only use lf as textline separator.
            int[] codes = new int[lines.Length];
            int lastUsedCode = h.Count;

            string s;
            for (int i = 0; i < lines.Length; ++i)
            {
                s = lines[i];

                if (trimSpace)
                    s = s.Trim();

                if (ignoreSpace)
                    s = Regex.Replace(s, "\\s+", " "); // TODO: optimization: faster blank removal.

                if (ignoreCase)
                    s = s.ToLower();

                if (h[s] == null)
                {
                    lastUsedCode++;
                    h[s] = lastUsedCode;
                    codes[i] = lastUsedCode;
                }
                else
                {
                    codes[i] = (int)h[s];
                }
            }
            return codes;
        }

        /// <summary>
        /// This is the algorithm to find the Shortest Middle Snake (SMS).
        /// </summary>
        /// <param name="dataA">sequence A</param>
        /// <param name="lowerA">lower bound of the actual range in DataA</param>
        /// <param name="upperA">upper bound of the actual range in DataA (exclusive)</param>
        /// <param name="dataB">sequence B</param>
        /// <param name="lowerB">lower bound of the actual range in DataB</param>
        /// <param name="upperB">upper bound of the actual range in DataB (exclusive)</param>
        /// <param name="downVector">a vector for the (0,0) to (x,y) search. Passed as a parameter for speed reasons.</param>
        /// <param name="upVector">a vector for the (u,v) to (N,M) search. Passed as a parameter for speed reasons.</param>
        /// <returns>a MiddleSnakeData record containing x,y and u,v</returns>
        private static ShortestMiddleSnake GetShortestMiddleSnake(DiffData dataA, int lowerA, int upperA, DiffData dataB, int lowerB, int upperB, int[] downVector, int[] upVector)
        {
            ShortestMiddleSnake shortestMiddleSnake;
            int max = dataA.Length + dataB.Length + 1;

            int downK = lowerA - lowerB; // the k-line to start the forward search
            int upK = upperA - upperB; // the k-line to start the reverse search

            bool isOddDelta = (((upperA - lowerA) - (upperB - lowerB)) & 1) != 0;

            // The vectors in the publication accepts negative indexes. the vectors implemented here are 0-based
            // and are access using a specific offset: UpOffset UpVector and DownOffset for DownVektor
            int downOffset = max - downK;
            int upOffset = max - upK;

            int maxD = ((upperA - lowerA + upperB - lowerB) / 2) + 1;

            // init vectors
            downVector[downOffset + downK + 1] = lowerA;
            upVector[upOffset + upK - 1] = upperA;

            for (int D = 0; D <= maxD; D++)
            {

                // Extend the forward path.
                for (int k = downK - D; k <= downK + D; k += 2)
                {
                    // find the only or better starting point
                    int x, y;
                    if (k == downK - D)
                    {
                        x = downVector[downOffset + k + 1]; // down
                    }
                    else
                    {
                        x = downVector[downOffset + k - 1] + 1; // a step to the right
                        if ((k < downK + D) && (downVector[downOffset + k + 1] >= x))
                            x = downVector[downOffset + k + 1]; // down
                    }
                    y = x - k;

                    // find the end of the furthest reaching forward D-path in diagonal k.
                    while ((x < upperA) && (y < upperB) && (dataA.Data[x] == dataB.Data[y]))
                    {
                        x++; y++;
                    }
                    downVector[downOffset + k] = x;

                    // overlap ?
                    if (isOddDelta && (upK - D < k) && (k < upK + D))
                    {
                        if (upVector[upOffset + k] <= downVector[downOffset + k])
                        {
                            shortestMiddleSnake.x = downVector[downOffset + k];
                            shortestMiddleSnake.y = downVector[downOffset + k] - k;
                            return (shortestMiddleSnake);
                        }
                    }

                }

                // Extend the reverse path.
                for (int k = upK - D; k <= upK + D; k += 2)
                {
                    // find the only or better starting point
                    int x, y;
                    if (k == upK + D)
                    {
                        x = upVector[upOffset + k - 1]; // up
                    }
                    else
                    {
                        x = upVector[upOffset + k + 1] - 1; // left
                        if ((k > upK - D) && (upVector[upOffset + k - 1] < x))
                            x = upVector[upOffset + k - 1]; // up
                    } // if
                    y = x - k;

                    while ((x > lowerA) && (y > lowerB) && (dataA.Data[x - 1] == dataB.Data[y - 1]))
                    {
                        x--; y--; // diagonal
                    }
                    upVector[upOffset + k] = x;

                    // overlap ?
                    if (!isOddDelta && (downK - D <= k) && (k <= downK + D))
                    {
                        if (upVector[upOffset + k] <= downVector[downOffset + k])
                        {
                            shortestMiddleSnake.x = downVector[downOffset + k];
                            shortestMiddleSnake.y = downVector[downOffset + k] - k;
                            return (shortestMiddleSnake);
                        }
                    }
                }
            }
            throw new ApplicationException("Failed to compute the shortest middle snake.");
        }


        /// <summary>
        /// This is the divide-and-conquer implementation of the longes common-subsequence (LCS) 
        /// algorithm.
        /// The published algorithm passes recursively parts of the A and B sequences.
        /// To avoid copying these arrays the lower and upper bounds are passed while the sequences stay constant.
        /// </summary>
        /// <param name="dataA">sequence A</param>
        /// <param name="lowerA">lower bound of the actual range in DataA</param>
        /// <param name="upperA">upper bound of the actual range in DataA (exclusive)</param>
        /// <param name="dataB">sequence B</param>
        /// <param name="lowerB">lower bound of the actual range in DataB</param>
        /// <param name="upperB">upper bound of the actual range in DataB (exclusive)</param>
        /// <param name="downVector">a vector for the (0,0) to (x,y) search. Passed as a parameter for speed reasons.</param>
        /// <param name="upVector">a vector for the (u,v) to (N,M) search. Passed as a parameter for speed reasons.</param>
        private static void LongesCommonSubsequence(DiffData dataA, int lowerA, int upperA, DiffData dataB, int lowerB, int upperB, int[] downVector, int[] upVector)
        {
            // Fast walkthrough equal lines at the start
            while (lowerA < upperA && lowerB < upperB && dataA.Data[lowerA] == dataB.Data[lowerB])
            {
                lowerA++; lowerB++;
            }

            // Fast walkthrough equal lines at the end
            while (lowerA < upperA && lowerB < upperB && dataA.Data[upperA - 1] == dataB.Data[upperB - 1])
            {
                --upperA; --upperB;
            }

            if (lowerA == upperA)
            {
                // mark as inserted lines.
                while (lowerB < upperB)
                    dataB.Modified[lowerB++] = true;

            }
            else if (lowerB == upperB)
            {
                // mark as deleted lines.
                while (lowerA < upperA)
                    dataA.Modified[lowerA++] = true;
            }
            else
            {
                // Find the middle snakea and length of an optimal path for A and B
                ShortestMiddleSnake shortestMiddleSnake = GetShortestMiddleSnake(dataA, lowerA, upperA, dataB, lowerB, upperB, downVector, upVector);
                
                // The path is from LowerX to (x,y) and (x,y) to UpperX
                LongesCommonSubsequence(dataA, lowerA, shortestMiddleSnake.x, dataB, lowerB, shortestMiddleSnake.y, downVector, upVector);
                LongesCommonSubsequence(dataA, shortestMiddleSnake.x, upperA, dataB, shortestMiddleSnake.y, upperB, downVector, upVector);  // 2002.09.20: no need for 2 points 
            }
        }


        /// <summary>Scan the tables of which lines are inserted and deleted,
        /// producing an edit script in forward order.  
        /// </summary>
        /// dynamic array
        private static List<Item> CreateDiffs(DiffData dataA, DiffData dataB)
        {
            List<Item> differences = new List<Item>();
            int lineA = 0, lineB = 0;
            while (lineA < dataA.Length || lineB < dataB.Length)
            {
                if ((lineA < dataA.Length) && (!dataA.Modified[lineA])
                  && (lineB < dataB.Length) && (!dataB.Modified[lineB]))
                {
                    // equal lines
                    lineA++;
                    lineB++;
                }
                else
                {
                    // maybe deleted and/or inserted lines
                    int startA = lineA, startB = lineB;

                    while (lineA < dataA.Length && (lineB >= dataB.Length || dataA.Modified[lineA]))
                        // while (lineA < DataA.Length && DataA.Modified[lineA])
                        lineA++;

                    while (lineB < dataB.Length && (lineA >= dataA.Length || dataB.Modified[lineB]))
                        // while (lineB < DataB.Length && DataB.Modified[lineB])
                        lineB++;

                    if ((startA < lineA) || (startB < lineB))
                    {
                        // store a new difference-item
                        Item item = new Item();
                        item.StartA = startA;
                        item.StartB = startB;
                        item.DeletedA = lineA - startA;
                        item.InsertedB = lineB - startB;
                        differences.Add(item);
                    }
                }
            }
            return differences;
        }

    } // class Diff

    /// <summary>Data on one input file being compared.  
    /// </summary>
    internal class DiffData
    {

        /// <summary>Number of elements (lines).</summary>
        internal int Length;

        /// <summary>Buffer of numbers that will be compared.</summary>
        internal int[] Data;

        /// <summary>
        /// Array of booleans that flag for modified data.
        /// This is the result of the diff.
        /// This means deletedA in the first Data or inserted in the second Data.
        /// </summary>
        internal bool[] Modified;

        /// <summary>
        /// Initialize the Diff-Data buffer.
        /// </summary>
        /// <param name="initData">reference to the buffer</param>
        internal DiffData(int[] initData)
        {
            Data = initData;
            Length = initData.Length;
            Modified = new bool[Length + 2];
        }

    }
}